package features.advance.leetcode.tree.medium;

import features.advance.leetcode.tree.model.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 *  剑指 Offer 07. 重建二叉树
 *
 *  难度：中等
 *
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 *
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 5000
 *
 *
 *
 * 注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 *
 * @author LIN
 * @date 2021-06-19
 */
public class Offer07 {
    public static void main(String[] args) {
        int[] preorder = {3,9,8,6,4,10,20,15,7};
        int[] inorder = {4,5,8,10,9,3,15,20,7};

        Solution solution = new Solution(){
            int inp = 0, prep = 0;
            @Override
            public TreeNode buildTree(int[] preorder, int[] inorder) {
                return buildTree2(preorder,inorder);
            }
            //三指针法，对preoder双指针，对inorder单指针，其中有一个指针是每个节点的值
            public TreeNode buildTree2(int[] preorder,int[] inorder){
                return build2(preorder,inorder,Integer.MAX_VALUE);
            }
            public TreeNode<Integer> build2(int[] preorder,int[] inorder,int stop){
                if(prep >= preorder.length) return null;
                //如果递归指针与中序相等，说明左树完结，返回
                if(inorder[inp] == stop){ inp++; return null;}
                //节点的值作为指针，递归返回就是指针后退，递归往下就是指针往前
                TreeNode<Integer> node = new TreeNode(preorder[prep++]);
                node.left = build2(preorder,inorder,node.val);
                node.right = build2(preorder,inorder,stop);
                return node;
            }

        };
        TreeNode<Integer> treeNode1 = solution.buildTree(preorder, inorder);
        System.out.println(treeNode1);
        solution = new Solution() {
            @Override
            public TreeNode buildTree(int[] preorder, int[] inorder) {
                if (preorder == null || preorder.length == 0) {
                    return null;
                }
                TreeNode<Integer> root = new TreeNode(preorder[0]);
                Deque<TreeNode<Integer>> stack = new LinkedList<TreeNode<Integer>>();
                stack.push(root);
                int inorderIndex = 0;
                for (int i = 1; i < preorder.length; i++) {
                    int preorderVal = preorder[i];
                    TreeNode<Integer> node = stack.peek();
                    if (node.val != inorder[inorderIndex]) {
                        node.left = new TreeNode(preorderVal);
                        stack.push(node.left);
                    } else {
                        while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                            node = stack.pop();
                            inorderIndex++;
                        }
                        node.right = new TreeNode(preorderVal);
                        stack.push(node.right);
                    }
                }
                return root;
            }
        };


        TreeNode<Integer> treeNode = solution.buildTree(preorder, inorder);
        System.out.println(treeNode);

    }

    static class Solution {
        /**
         * 方法一：递归
         * 思路
         *
         * 对于任意一颗树而言，前序遍历的形式总是
         *
         * [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
         * 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
         *
         *
         * [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
         * 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。
         * 由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历
         * 的结果中，对上述形式中的所有左右括号进行定位。
         *
         * 这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和
         * 中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
         *
         *
         * @param preorder
         * @param inorder
         * @return
         */
        public TreeNode<Integer> buildTree(int[] preorder, int[] inorder) {

            return null;
        }
    }

}
